package BackTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 组合总和39 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp =new ArrayList<>();
    int[] nums;
    int tar;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        nums = candidates;
        Arrays.sort(nums);
        tar = target;
            // startIndex(去 重复set, 必须在main里初始for实现，递归里实现不了)
            // sum(if末卡用的 上轮tmp-sum对应)
            backTrack(0, 0);
        return res;
    }
    void backTrack(int startIndex, int sum) {
        if(sum == tar){
            res.add(new ArrayList<>(tmp));
            return;
        }else if(sum > tar){
            return;
        }
        for (int i = startIndex; i < nums.length
                /**
                 * 表面看起来是 超一轮 收集 res
                 *
                 * -> 其实是 下一轮if卡住了 没走for（其实没超）
                 */
                && sum+nums[i] <= tar
                ; i++) {
            tmp.add(nums[i]);
            sum += nums[i];
            /**
             * 是i，不是sI
             *
             * 因为递归内部的每个块，
             * 也要从本身i走，
             *
             * 即 内部for 和 起点for 相同逻辑（难想到）
             *
             */
            backTrack(i, sum);
            sum -= nums[i];
            tmp.remove(tmp.size()-1);
        }
    }

    @Test
    public void t(){
        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
    }
}
